// 钢条切割
use std::collections::HashMap;
use std::cmp;
// from top 2 bottom
pub fn cut_rob_top(rubs:&HashMap<i32,i32>,length:i32)->i32{
    if length == 0 {
        return 0
    }
    let mut p:i32 = -1;
    for i in 1..(length+1) {
        p = cmp::max(p,rubs.get(&i).unwrap() + cut_rob(rubs,length-i));
    }
    p
}


pub fn cut_rob(rubs:&HashMap<i32,i32>,length:i32)->i32{
    cut_rob_top(rubs,length)
}
// top_mem
fn cut_rob_mem(rubs:&HashMap<i32,i32>,length:i32,mem:&mut HashMap<i32,i32>)->i32{
    if length == 0 {
        return 0
    }
    if let Some(price) = mem.get(&length) {
        return price.clone()
    }
    let mut p:i32 = -1;
    for i in 1..(length+1) {
        p = cmp::max(p,rubs.get(&i).unwrap() + cut_rob_mem(rubs,length-i,mem));
    }
    mem.insert(length,p);
    p
}

//bottom
fn cut_rob_bottom(rubs:&HashMap<i32,i32>,length:i32)->i32 {
    let mut r = vec![0;(length+1) as usize];
    for i in 1..(length+1) {
        let mut p = -1;
        for j in 1..(i+1) {
            p = cmp::max(p,rubs.get(&j).unwrap()+ r[(i-j) as usize]);
        }
        r[i as usize] = p;
    }
    r[length as usize]
}
